/*
  Bunch of classes to implement circle packing.
  
  2 versions:
  ===========
  SimpleCirclePacker: quick and dirty.
  CirclePacker: full blown version

*/


 
/*
  SimpleCirclePacker
  ===================
  This lot does some quick and dirty circle packing based on the twin ideas of
  attraction (gravity towards the centre) and repulsion (no intersecting circles). 
  Works great until you have 100's of nodes in which case it starts to really
  chew up the cpu cycles.

*/
 
class CPNode {
 
   int x;
   int y;
   int radius;
   int ncolor;
   String title;
   
   CPNode(int x, int y, int radius, color ncolor, String title) {
     this.x = x;
     this.y = y;
     this.radius = radius;
     this.ncolor = ncolor;
     this.title = title;
   }
   
   CPNode(int x, int y, int radius, color ncolor) {
     this(x,y,radius,ncolor,null);
   }
   
   String getTitle() {
     return this.title;  
   }
        
   void draw() {
     smooth();
     noStroke();
     fill(ncolor);
     ellipse(x,y,radius*2,radius*2);
   }
}

class CentreComparator implements Comparator {
  
   int cx;
   int cy;
   
   // assume rectangle shape for now
   public void setSize(int width, int height) {
     this.cx = width / 2;
     this.cy = height / 2;  
   }
   
   float distance(CPNode node) {
      return dist(node.x, node.y, this.cx, this.cy);
   }
   
   public int compare(Object o1, Object o2) {
    CPNode node1 = (CPNode) o1;
    CPNode node2 = (CPNode) o2;
    float dist1 = distance(node1);
    float dist2 = distance(node2);
    int res;
    if (dist1 < dist2)
      res = -1;
    else if (dist1 > dist2)
      res = 1;
    else
      res = 0;
    return res;
  }     
  
}

CentreComparator nodeComp = new CentreComparator();
   
class SimpleCirclePacker {
  
  ArrayList nodes;
  
  float easing = 0.1;
  
  SimpleCirclePacker() {
    this.nodes = new ArrayList();
  }  
  
  void add(CPNode node) {
    nodes.add(node);
  }
  
  void add(int x, int y, int radius, color ncolor) {
    add(new CPNode(x,y,radius,ncolor));  
  }
  
  void add(int x, int y, int radius, color ncolor,String title) {
    add(new CPNode(x,y,radius,ncolor,title));  
  }

  
  void pack(int swidth, int sheight) {
    
    nodeComp.setSize(swidth,sheight);
    
    // to do sort by distance to centre
    Collections.sort(nodes, nodeComp);
    
    for (int i=0; i < nodes.size(); i++) {
       CPNode nodea = (CPNode) nodes.get(i);
       for (int j=i+1; j < nodes.size(); j++) {
         CPNode nodeb = (CPNode) nodes.get(j);
         float cdist = dist(nodea.x,nodea.y,nodeb.x,nodeb.y); 
         int rsum = nodea.radius + nodeb.radius;
         // circles intersect
         if (cdist < rsum) {
           println("nodes intersect cdist " + cdist + " < rsum "+ rsum);
           // first normalize, then scale distance to move, then half it
           float dx = ((nodeb.x - nodea.x) / cdist) * (rsum - cdist) * 0.5;
           float dy = ((nodeb.y - nodea.y) / cdist) * (rsum - cdist) * 0.5;
           println("move apart dx="+dx + " dy="+dy);
           // move a
           nodea.x -= dx;
           nodea.y -= dy;
           println("nodea x="+nodea.x+" y=" + nodea.y); 
           // move b
           nodeb.x += dx;
           nodeb.y += dy;
           println("nodeb x="+nodeb.x+" y=" + nodeb.y); 
         }
       }
    }
    
    /* starting with the closest try and move all circles towards centre */
    int cx = width / 2;
    int cy = height / 2;
    for (int i=0; i < nodes.size(); i++) {
      CPNode node = (CPNode) nodes.get(i);  
      float dx = (node.x - cx) * easing;
      float dy = (node.y - cy) * easing;
      println("node x="+node.x+" y=" + node.y); 
      println("move dx="+dx + " dy=" + dy);
      node.x -= dx;
      node.y -= dy;  
    }  
  }
  
  void draw() {
    background(255);
    for (int i=0; i < nodes.size(); i++) {
      CPNode node = (CPNode) nodes.get(i);
      node.draw();
    }
  }  
}


/*
  CirclePacker
  ============
  A proper implementation of circle packing based on the ideas described
  in the paper "Visualization of Large Hierarchial Data by Circle Packing"
  written by Wang et Al and submitted to at the April 2006 SIGCHI conference.
  
  After spending a whole day on this I now understand why "circle packing" 
  is considered a very complex subject.
  
  Sample usage:
  =============
  
  // create packer
  CirclePacker packer = new CirclePacker();
  packer.setBounds(0,0,width,height);
  packer.setData(node);
  // these methods should be called by main loop
  packer.update();
  packer.draw();
 
  
*/


class CircleElem implements Comparable {

  // related to circular chain list
  private CircleElem next;
  private CircleElem prev;
     
  // 2 nodes a&b (insert c betweeen them)
  public void insert(CircleElem elem) {
    CircleElem tmp = next;
    next = elem;
    elem.prev = this;
    elem.next = tmp;
    tmp.prev = elem;
  }
    
  public void remove() {
    // link next in list to previous
    next.prev = prev;
    prev.next = next;
    this.next = this.prev = null;
  }
  
  public CircleElem prev() {
    return this.prev;  
  }
  
  public CircleElem next() {
    return this.next;  
  }
  
  public void join(CircleElem to) {
    CircleElem elem,next;
    for (elem = this.next; elem != to; elem = next) {
      next = elem.next;
      elem.remove();
    }
    this.next = to;
    to.prev = this;
  }

  public void cut() {
    this.next = this.prev = null;
  }

  public void wrap() {
    this.next = this.prev = this;
  }

  // related to drawing circle  
  float x;
  float y;
  float radius;
  color ncolor;
  
  // node we represent
  private DataNode dataNode;
  
  public CircleElem(float radius, DataNode dataNode, color ncolor) {
    this.next = this.prev = null;
    this.radius = radius;
    this.dataNode = dataNode;
    this.ncolor = ncolor;
  }
  
  
  public boolean intersects(CircleElem a) {
    float dx = a.x - this.x;
    float dy = a.y - this.y;
    float sr = a.radius + this.radius;
    return (dx*dx + dy*dy) < (sr*sr - 0.001);
  }
  
  public void draw(PGraphics pg) {
     pg.smooth();
     pg.noStroke();
     pg.fill(ncolor);
     pg.ellipse(x,y,radius*2, radius*2);
     // need to show name inside circle as it appears on screen
     float x1 = pg.screenX(x-radius,y-radius);
     float y1 = pg.screenY(x-radius,y-radius);
     float x2 = pg.screenX(x+radius,y+radius);
     float y2= pg.screenY(x+radius,y+radius);
     pg.pushMatrix();
     pg.resetMatrix();
     pg.fill(0);
     pg.textFont(defaultFont);
     pg.textAlign(CENTER,CENTER);
     pg.text(dataNode.getName(),x1,y1,x2-x1,y2-y1);
     pg.popMatrix();
  }
  
  boolean bad() {
    return (Float.isNaN(x) || Float.isNaN(y) || Float.isNaN(radius));
  }
  
  String toString() {
    return "x="+x+"y="+y+"radius="+radius+"node="+dataNode;
  }
  
  public int compareTo(Object o) {
    CircleElem elem = (CircleElem) o;
    float tmp = this.radius - elem.radius;
    if (tmp < 0) return -1;
    if (tmp > 0) return 1;
    return 0;
  }
}

public class ColorMate {
  color ncolor;
  float radius;
  public ColorMate(color ncolor, float radius) {
    this.ncolor = ncolor;
    this.radius = radius;
  }  
}

class CirclePacker extends AWidget implements AWidgetListener {
  
  // circle elements
  private ArrayList chains;
  private HashMap stateMap;
  
  // our view we can draw inside
  private int bx,by,bwidth,bheight;
  
  // our very private little world
  private PGraphics pg;
  private PImage imageCache;
  
  private DataNode rootNode;
  private DataFilter filter;
  private boolean dataChanged;
  
  // track world box co-ords of elems
  private float startX,startY,endX, endY;

  private boolean showChain = false;
  private float branchRadius = 20;
  private float leafRadius = 100;
  private int maxLevel = 0; //Integer.MAX_VALUE;
 
  // used to translate and scale objects to current view
  private float transX;
  private float transY;  
  private float zoomXY;
 
  private AScrollBar horizBar;
  private AScrollBar vertBar;
  private ASlideBar zoomBar;
 
  public CirclePacker() {
    this.chains = new ArrayList();
    this.stateMap = new HashMap();
    this.rootNode = null;
  }
  
  public void setBounds(int bx, int by, int bwidth, int bheight) { 
    this.bx = bx;
    this.by = by;
    this.bwidth = bwidth;
    this.bheight = bheight;
    this.pg = createGraphics(bwidth, bheight,JAVA2D);
    this.imageCache = null;
  }

  public void setData(DataNode rootNode) {
    this.rootNode = rootNode;
    this.dataChanged = true;
  }
  
  public void setFilter(DataFilter filter) {
    this.filter = filter;  
    this.dataChanged = true;
  }
   
  public void setHorizBar(AScrollBar horizBar) {
    this.horizBar = horizBar;
    horizBar.setBounds(bx, by+bheight, bwidth, HBAR_HEIGHT); 
    horizBar.setListener(this);
  }
  
  public void setVertBar(AScrollBar vertBar) {
    this.vertBar = vertBar;
    vertBar.setBounds(bx+bwidth,by,VBAR_WIDTH, bheight); 
    vertBar.setListener(this);
  }
  
  public void setZoomBar(ASlideBar zoomBar) {
    this.zoomBar = zoomBar;
    zoomBar.setBounds(bx,by-ZBAR_HEIGHT,bwidth, ZBAR_HEIGHT);
    zoomBar.setListener(this);
  }
  
  public void setShowChain(boolean showChain) {
    this.showChain = showChain;
    this.imageCache = null;  
  }
  
  public void setMaxLevel(int maxLevel) {
    this.maxLevel = maxLevel;  
    this.dataChanged = true;
  }
  
  public void setLeafRadius(int leafRadius) {
    this.leafRadius = leafRadius;
  }
  
  public int getX() {
    return bx;
  }
  
  public int getY() {
    return by;
  }
  
  public int getWidth() {
    return bwidth;
  }
  
  public int getHeight() {
    return bheight;
  }
  
  private void resetData() {
    // prevent memory leaks
    CircleElem start,next,elem;
    for (int i=0; i<chains.size(); i++) {
      start = (CircleElem) chains.get(i);
      for (elem = start.next; elem != start; elem = next) {
        next = elem.next;
        elem.remove();
      }
      start.remove();      
    }
    chains.clear();
    // TODO: iterate over entires and delete DataNode refs
    stateMap.clear();
  }
    
  public void valueChanged(AWidget widget) {
    println("valueChanged"+widget);
    if (widget == horizBar) {
      transX = bwidth/2 + horizBar.getValue();
      this.imageCache = null;
    }
    else if (widget == vertBar) {
      transY = bheight/2 + vertBar.getValue();
      this.imageCache = null;
    }
    else if (widget == zoomBar) {
      if (rootNode == null) return;
      CircleElem rootElem = (CircleElem) stateMap.get(rootNode);
      float diam = rootElem.radius * 2;
      float maxZoom = (bheight > bwidth) ? diam / bwidth : diam / bheight;
      zoomXY = zoomBar.getValue();
      if (zoomXY > maxZoom) {
        zoomXY = maxZoom;  
      }
      float scaleXY = 1/zoomXY;
      transX = bwidth/2;
      transY = bheight/2;
      // need to recalc x,y trans
      println("diam="+diam+" maxZoom="+maxZoom+ " zoomXY="+zoomXY+" scaleXY="+scaleXY+" transX="+transX+" transY="+transY);
      updateScroll(scaleXY);
      this.imageCache = null;
    }
    else  {
      println("aargh!"+widget); 
    }
  }
  
  private void updateScroll(float scaleXY) {
    if (vertBar != null) {
      vertBar.setValues(round(startY*scaleXY), round(endY*scaleXY), 0, bheight);   
    }
    if (horizBar != null) {
      horizBar.setValues(round(startX*scaleXY), round(endX*scaleXY), 0, bwidth);   
    }  
  }
  
  public void update() {
    if (dataChanged) {
      dataChanged = false;
      resetData();
      if (rootNode != null) {
        updateData();  
      }
      // setting this to null will trigger a MULTIUDE of redraws
      this.imageCache = null;
    }
    // do gui stuff here (e.g mouse stuff)
  }
  
  // ONLY call this if data has changed
  private void updateData() {
    println("updateData");
    CircleElem rootElem = packDataNode(rootNode, 0);
    stateMap.put(rootNode, rootElem);
    resetBox();
    
    // centre everthing around view centre
    rootElem.x = 0;
    rootElem.y = 0;    
    calcBox(rootElem);
    reposNodes(rootNode, rootElem.x, rootElem.y, 0);
    
    println(String.format("box spos=(%f,%f) epos(%f,%f) width=%f height=%f",startX,startY,endX,endY,endX-startX, endY-startY));
    
    // new world - reset translations
    float diam = rootElem.radius * 2;
    float maxZoom = (bheight > bwidth) ? diam / bwidth : diam / bheight;
    float scaleXY = 1 / maxZoom;
    
    // always centre view in the centre of the world
    transX = bwidth/2; 
    transY = bheight/2;
    zoomXY = maxZoom;
 
    println("diam="+diam+" zoomXY="+zoomXY+"scaleXY="+scaleXY+" transX="+transX+" transY="+transY);
    
    if (zoomBar != null) {
      zoomBar.setValues(1, max(1,ceil(maxZoom)), ceil(zoomXY));   
    }
    
    updateScroll(scaleXY);    
  }
 
  private CircleElem packDataNode(DataNode node,int level) {
    ArrayList elems = new ArrayList();  
    int numChains = chains.size();
    DataNodeIterator itor = node.iterator(filter);
    while (itor.hasNext()) {
      DataNode childNode = itor.next();
      CircleElem elem = packDataNode(childNode,level+1); 
      if (elem != null) {
        elems.add(elem);
      }
    }
    
    float radius;
    
    float hue = map(level, 0, maxLevel, 0, 128);
    color ncolor = color(hue,128,200);
    HashMap colors = new HashMap();
     
    if (elems.size() == 0) {
      // cull any branch node > level 0  with no leafs
      if (!node.isLeaf() && level > 0) {
        return null;
      }
      radius = leafRadius;
    }
    else if (level == maxLevel) {
       // gone to far need to discard some data
       radius = leafRadius * elems.size(); 
    }
    else if (level < maxLevel) {
      // sort list
      Collections.sort(elems);
      CircleElem chainStart = packCircle(elems);
      traceBox(elems, chainStart);
      radius = calcMaxRadius(elems);
      if (chainStart != null) {
        chains.add(chainStart);
      }
      // hack to ensure circles with the same radius have same color
      for(int i=0; i < elems.size(); i++) {
        CircleElem child = (CircleElem) elems.get(i);
        ColorMate mate = (ColorMate) colors.get(new Float(child.radius));  
        if (mate == null) {
          mate = new ColorMate(color(random(0,255),128,220),child.radius);
          colors.put(new Float(mate.radius), mate); 
        }
        child.ncolor = mate.ncolor;
      }
    }
    else {
      // level > maxLevel need only a dummy circle flag valid data
      radius = 0;
      node = null;  
    }
    
    CircleElem elem = new CircleElem(radius, node, ncolor);  
    if (node != null) {
      stateMap.put(node, elem);
    }
    
    return elem;
  }

  private void resetBox() {
    this.startX = this.startY = Float.MAX_VALUE;
    this.endX = this.endY = Float.MIN_VALUE;
  }
  
  private void traceBox(ArrayList elems, CircleElem chainStart) {
    resetBox();
    CircleElem elem;
    if (chainStart == null) {
      for (int i=0; i< elems.size(); i++) {
        elem = (CircleElem) elems.get(i);
        calcBox(elem);
      }
    }
    else {
      // traverse the nodes front chain
      elem = chainStart;
      do {
        calcBox(elem);
        elem = elem.next();
      } while(elem != chainStart);
    }
  }
  
  // need to recenter the circles around the box centre (not 0,0)
  private float calcMaxRadius(ArrayList elems) {
    float x = (startX + endX) / 2;
    float y = (startY + endY) / 2;
    float originDist;
    float radius;
    float maxRadius = 0;
    
    for (int i=0; i < elems.size(); i++) {
      CircleElem elem = (CircleElem) elems.get(i);
      elem.x -= x;
      elem.y -= y;
      originDist = sqrt(elem.x*elem.x+elem.y*elem.y);
      radius = elem.radius + originDist;
      if (radius > maxRadius) {
        maxRadius = radius;
      }
    } 
    
    return maxRadius;
  }
  
  private void calcBox(CircleElem elem) {
    float tmp;
    // top left
    tmp = elem.x - elem.radius; 
    if (tmp < startX) startX = tmp;
    tmp = elem.y - elem.radius;
    if (tmp < startY) startY = tmp;
    // bottom right
    tmp = elem.x + elem.radius;
    if (tmp > endX) endX = tmp;
    tmp = elem.y + elem.radius;
    if (tmp > endY) endY = tmp;
  }
  
  public CircleElem getElem(ArrayList elems, int idx) {
    return idx < elems.size() ? (CircleElem) elems.get(idx) : null;
  }
  
  private CircleElem packCircle(ArrayList elems) {
    
    CircleElem cm,cn,ci,cj,elem;
    int nstep,mstep;
    
    // first place cm to the left of origin
    if ( (cm = getElem(elems,0)) == null) return null;
    cm.x = -cm.radius;
    cm.y = 0;
    
    // now place cn to the right of the origin
    if ( (cn = getElem(elems,1)) == null) return null;
    cn.x = cn.radius;
    cn.y = 0;
    
    // now place c tangent to a and b
    if ((ci = getElem(elems,2)) == null) return null;
    arrange(cm,cn,ci);

    cm.wrap();
    cm.insert(ci);
    ci.insert(cn);
    cn = cm.next();
  
    // rearrange the rest
    for (int i=3; i < elems.size(); i++) {
      ci = getElem(elems,i);   
      if (cm == cn) {
        println("trouble " + i + "/" + elems.size() +  " cm=cn " + cm);
      }
      arrange(cm,cn,ci);
      // now forward search chain after cn for cj intersect
      cj = null;
      nstep = 0;
      for (elem = cn.next(); elem != cn; elem = elem.next(), nstep++) {
        if (elem == cm) {
          continue;  
        }
        if (ci.intersects(elem)) {
          cj = elem;
          break;
        }
      }
      if (cj != null) {
        // must backward search chain before cm for cj intersect
        for (elem = cm.prev(),mstep=0; elem != cj.prev(); elem = elem.prev(),mstep++) {
          if (ci.intersects(elem) && mstep < nstep) {
            cj = elem;
            nstep = -1;
            break;
          }
        }
      }
      if (cj == null) {
        // add chain link
        cm.insert(ci);
        cn = ci;
      }
      else {
        // remove some chain links        
        if (nstep < 0) {
          // drop chain segment between cj and cn
          cj.join(cn);
          cm = cj;
        }
        else {
          // drop chain segment between cm and cj
          cm.join(cj);
          cn = cj;
        }
        // neet to try again
        --i;
      }
    } // for
    // save front chain start
    return cm;
  }
    
  /* 
    Arrange circle c so that its tangent to both circles a & b.
    Maths in here requires a small boat load of tangent circle trigonometry.
    Have a look though at whats involved in the Koebe–Andreev–Thurston theorem if you 
    think this code causes some head scratching! 
    Good place to start reading about circle packing is http://www.math.utk.edu/~kens.   
  */
  public void arrange(CircleElem elemA, CircleElem elemB, CircleElem elemC) {
  
      float sideA,sideB,sideC;
      float dx,dy;
      float cosA,angleA;
      float sideAdj,sideOpp;

      // calc triangle side lengths
      sideA = elemB.radius + elemC.radius;
      sideB = elemA.radius + elemC.radius;
      sideC = dist(elemA.x,elemA.y, elemB.x,elemB.y);
      
      // calc unit vector (i.e normalize dist vector between A&B
      dx = (elemB.x - elemA.x) / sideC;
      dy = (elemB.y - elemA.y)  / sideC;
                 
      // do cosine rule cos A=(b^2 + c^2 - a^2) / 2bc
      cosA = (sideB * sideB + sideC * sideC  - sideA * sideA) /  (2*sideB*sideC);
      angleA = acos(cosA); // radians!
      
      // now get right angle triangle opposite&adjacent sides lengths from A & hyptoneuse sideB
      sideAdj = cosA * sideB;
      sideOpp = sin(angleA) * sideB;

      // now make node C tangent to A&B
      elemC.x = (elemA.x + sideAdj*dx) + sideOpp*dy;
      elemC.y = (elemA.y + sideAdj*dy) - sideOpp*dx;
      
      if (elemA.bad() || elemB.bad() || elemC.bad()) {
       println(String.format(
          "[Arrange]\n"+
          "elemA(%s)\nNodeB(%s)\nNodeC(%s)\n" + 
          "sideA=%f sideB=%f sideC=%f\n"+
          "dx=%f dy=%f\n" +
          "cosA=%f angleA=%f\n" +
          "sideAdj=%f sideOpp=%f",
          elemA, elemB, elemC,
          sideA,sideB,sideC,
          dx,dy,
          cosA,angleA,
          sideAdj,sideOpp));   
      }
  }

  private void reposNodes(DataNode node, float dx, float dy, int level) {
    
    if (level >= maxLevel) return;
        
    DataNodeIterator itor = node.iterator(filter);
    while (itor.hasNext()) {
      DataNode childNode = itor.next();
      CircleElem elem = (CircleElem) stateMap.get(childNode); 
      if (elem != null) {
        elem.x += dx;
        elem.y += dy;
        calcBox(elem);
        reposNodes(childNode, elem.x, elem.y, level+1);
      }
    }    
  }
  
  // debug code
  private void dumpChain(String title, CircleElem chain) {
    println(title);
    CircleElem elem = chain;
    do {
      println(elem);
      elem = elem.next();
    } while(elem != chain) ;
  }
 
  // n.b all drawing done inside graphics buffer 
  public void draw() {
    if (imageCache == null) {
      drawData();
      imageCache = pg.get();
    }
    image(imageCache,bx, by);
  }
  
  private void drawData() {
    pg.beginDraw();
    pg.background(240);
    pg.fill(0);
    if (rootNode!=null) {
      drawCircles();  
      if (showChain) {
        drawChains();
      }
    }
    pg.endDraw();
  }
  
  private void doTransScale(CircleElem rootElem) {
    println("transScale");
    
    // find our circle's "world" scale to draw area bounds
    float diam = rootElem.radius * 2;
    float maxZoom = (bheight > bwidth) ? diam / bwidth : diam / bheight;    
     
    // sanitize zoom factor
    if (zoomXY > maxZoom) {
      zoomXY=maxZoom;  
    }

    // twice the world means half the view
    float scaleXY = 1/zoomXY;
    
    pg.translate(transX,transY);
    pg.scale(scaleXY, scaleXY);
    
    println("diam="+diam+" maxZoom="+maxZoom + " zoomXY="+zoomXY+" scaleXY="+scaleXY+" transX="+transX+" transY="+transY);
  }
  
  private void drawCircles() {
    CircleElem elem = (CircleElem) stateMap.get(rootNode);
    doTransScale(elem);
    elem.draw(pg);
    drawElems(rootNode, 0);
  }
  
  private void drawElems(DataNode node, int level) {
    if (level >= maxLevel) return; 
    DataNodeIterator itor = node.iterator(filter); 
    while (itor.hasNext()) {
      DataNode childNode = itor.next();
      CircleElem elem = (CircleElem) stateMap.get(childNode); 
      if (elem != null) {
        elem.draw(pg);
        drawElems(childNode, level+1);
      }
    }
  }
  
  private void drawChains() {
    for (int i=0; i < chains.size(); i++) {
      CircleElem chainStart = (CircleElem) chains.get(i);
      drawChain(chainStart);
    }  
  }
  
  private void drawChain(CircleElem chainStart) {
    CircleElem start,a,b;
    a = chainStart;
    b = a.next();
    pg.stroke(0);
    pg.strokeWeight(1);
    do {
      if (b != null) {
        pg.line(a.x,a.y,b.x,b.y);
        a = b;
        b = (CircleElem) b.next();
       }
     } while (a != chainStart && b != null);
  }
}
